package com.javabasic.algorithm.leetcode;

/**
 * @author mir.xiong
 * @version 1.0
 * @description
 * @see
 * @since Created by work on 2022/6/20 19:42
 */
public class MergeNodesInBetweenZeros {

    /**
     * 链表暴力解法，开辟新内存空间
     * @param head
     * @return
     */
    public ListNode mergeNodes(ListNode head) {

        ListNode result = new ListNode(0);
        ListNode tail = result;
        ListNode target;
        int sum = 0;
        while (head.next != null) {
            head = head.next;
            if (head.val != 0) {
                sum += head.val;
            } else {
                target = new ListNode(sum, tail.next);
                tail.next = target;
                tail = target;
                sum = 0;
            }
        }

        return result.next;
    }

    /**
     * 链表遍历+就地合并 不适用额外内存
     * @param head
     * @return
     */
    public ListNode mergeNodes2(ListNode head) {

        ListNode tempHead = head;
        ListNode preTempHead = head;
        ListNode lastPreNode = head;
        while (tempHead.next != null) {
            tempHead = tempHead.next;
            if (tempHead.val != 0) {
                preTempHead.val += tempHead.val;
                preTempHead.next = tempHead.next;
            } else {
                lastPreNode = preTempHead;
                preTempHead = tempHead;
            }
        }
        lastPreNode.next = null;
        return head;
    }
}


///**
// * Definition for singly-linked list.
// */
//public class ListNode {
//    int val;
//    ListNode next;
//    ListNode() {}
//    ListNode(int val) { this.val = val; }
//    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
//}
